// https://leetcode.cn/problems/maximum-frequency-stack/
// Created by ade on 2022/11/30.
//
#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;


class FreqStack {
public:
    /*unordered_map<int, vector<pair < int, int>>> q;
    int index = 0;

    FreqStack() {

    }

    void push(int val) {
        if (!q[val].empty()) {
            auto top = q[val].back();
            q[val].push_back({index, top.second + 1});
            if (top.second + 1 >= maxCount) {
                maxCount = top.second + 1;
            }
        } else {
            q[val].push_back({index, 1});
            if (maxCount < 1) {
                maxCount = 1;
                maxIndex = index;
            }
        }
        index++;
    }

    int pop() {
        int maxIndex = -1;
        int maxCount = 0;
        int res = -1;
        for (auto &iter:q) {
            if (iter.second.size() == 0) continue;
            if (iter.second.back().second > maxCount ||
                iter.second.back().second == maxCount && iter.second.back().first > maxIndex) {
                maxIndex = iter.second.back().first;
                maxCount = iter.second.back().second;
                res = iter.first;
            }
        }
        q[res].pop_back();
        return res;
    }*/
    unordered_map<int, int> freq;
    unordered_map<int, vector<int>> group;
    int maxNum = 0;

    FreqStack() {

    }

    void push(int val) {
        freq[val]++;
        maxNum = max(maxNum, freq[val]);
        group[freq[val]].push_back(val);
    }

    int pop() {
        int val = group[maxNum].back();
        freq[val]--;
        group[maxNum].pop_back();
        if (group[maxNum].empty()) maxNum--;
        return val;
    }
};

int main() {
    FreqStack f;
    f.push(4);
    f.push(0);
    f.push(9);
    f.push(3);
    f.push(4);
    f.push(2);
    f.pop();
    f.push(6);
    f.pop();
    f.push(1);
    f.pop();
    f.push(1);
    f.pop();
    f.push(4);
    f.pop();
    f.pop();
    f.pop();
    f.pop();
    f.pop();
    f.pop();
    return 0;
}
/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack* obj = new FreqStack();
 * obj->push(val);
 * int param_2 = obj->pop();
 */